package com.darrenchan.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-14 18:12
 */
public class Q93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> results = new ArrayList<>();
        if (s == null || s.length() < 4 || s.length() > 12) {
            return results;
        }

        dfs(s, 0, new ArrayList<>(), results);
        return results;
    }

    private void dfs(String s, int index, List<String> subsets, List<String> results) {
        if (index == s.length() && subsets.size() == 4) {
            String ip = String.join(".", subsets);
            results.add(ip);
        }
        for (int i = index; i < s.length() && i < index + 3; i++) {
            String substring = s.substring(index, i + 1);
            if (substring.startsWith("0")) {
                if ("0".equals(substring)) {
                    subsets.add(substring);
                    dfs(s, i + 1, subsets, results);
                    subsets.remove(subsets.size() - 1);
                }
            } else {
                if (Integer.parseInt(substring) >= 1 && Integer.parseInt(substring) <= 255) {
                    subsets.add(substring);
                    dfs(s, i + 1, subsets, results);
                    subsets.remove(subsets.size() - 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("111");
        list.add("222");
        list.add("333");
        list.add("444");

        System.out.println(String.join(".", list));
    }
}
